home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 9411 / CHIPKEDD.CD < prev    next >
Text File  |  1994-11-27  |  8KB  |  134 lines
  1.           @VKét rejtvényünk megoldásai@N
  2.  
  3.           @VCellák és nehéz szakaszok@N
  4.  
  5.           Ismét közöljük két régebbi feladványunk megoldását.
  6.  
  7.  
  8.  
  9.  
  10.           Júniusi   számunkban  jelent   meg   @KÅrva  bitek@N  címmel   a
  11.           következô    fizikai    eredetû   probléma:   egy   detektor
  12.           négyzetrácsba   rendezett   érzékelôkbôl   áll.   Ha   igazi
  13.           részecske  halad  át  rajta,  akkor  legalább két szomszédos
  14.           érzékelô  cella  állapota  1-re változik. Sajnos azonban egy
  15.           cella  véletlenszerûen  is  1 állapotba kerülhet az alap (0)
  16.           állapotból.  A  feladat  az, hogy megállapítsuk, mely pontok
  17.           tartoznak  a  zajhoz  (ôk  az ""árva bitek"), és töröljük ki
  18.           ezeket.  A  rejtvényre  öt  olvasónk  hat megfejtést küldött
  19.           be,  négy Pascal, egy-egy pedig C, Prolog nyelveken. Közülük
  20.           egy   hibásan   mûködött.   A   többi   program   sikeresnek
  21.           bizonyult:   hatalmas   tömböket   vizsgáltak  át  s  tettek
  22.           rendbe,   igen  rövid  idôk  alatt  --  természetesen  azért
  23.           akadtak  eltérések  mind  a  méretekben,  mind  a  tempóban.
  24.           (Továbbá  még  egy  csomó  egyéb  dologban:  van-e grafikus,
  25.           esetleg  karakteres  kijelzés, adatokat állományból olvassa,
  26.           vagy  klaviatúráról,  esetleg véletlen generálás történik és
  27.           így  tovább.) Kiderült (amint erre Matolcsi Tamás is utalt),
  28.           hogy   a   Prologot  nem  igazán  ilyen  típusú  feladatokra
  29.           találták  ki:  teljesítménye  a  közelébe  sem  ért  a többi
  30.           programnak (100x100-as ""távon" 40 sec.).
  31.  
  32.           Az  elsô,  tesztként használt 100x100-as tömböt 0,05 és 0,65
  33.           másodperc  közötti  idôk  alatt  pucolták  ki  a  ""többiek"
  34.           (386DX/40). A következô lépcsôként
  35.           alkalmazott  480  ezer  cella  esetében  0,6-2,5 másodpercre
  36.           volt  szükség  (érdekesség:  Matolcsi Tamás Pascal programja
  37.           nem  volt tekintettel a méretváltozásra, pontosan ugyanannyi
  38.           idô  --  0,65  s  --  kellett  a  majd ötvenszer akkora tömb
  39.           kezeléséhez.)   Az   egyik   csúcsteljesítmény   feltétlenül
  40.           Maleskovits  Péteré:  a  több mint 4 millió cellás detektort
  41.           nem  egészen  5  másodperc  alatt  elrendezi. A méretekben a
  42.           plafont  Matolcsi  Tamás  érte el, de ... ""A program kb. 16
  43.           milliárd   cellából  álló  detektorhálót  tud  kitisztítani,
  44.           amennyiben  van  a winchesteren ehhez elég hely (2 Gbyte) és
  45.           rendelkezünk  98  nap  szabad  gépidôvel  (386DX/40-en)."  A
  46.           többféle  lehetséges megoldási elv közül Maleskovits Péterét
  47.           tekintsük  meg. Programja az érzékelôket bitenként ábrázolja
  48.           (Word   típusú   mezôkben),   ehhez   az   oszlopok   számát
  49.           tizenhattal   oszthatóra   változtatja.  A  négyzetrácsot  a
  50.           heap-ben  tárolja,  így  az a szabad memóriától függôen akár
  51.           négymilló bitet is tartalmazhat.
  52.  
  53.           Az  algoritmus  lényege olvasónk megfogalmazásában: ""Minden
  54.           sor  vizsgálatánál  egy  akkora  méretû  Word típusú vektort
  55.           definiál  az  elsô  elem  memóriacímére, amely három egymást
  56.           követô  sort  lefed.  Ezután mindhárom sor elsô három elemét
  57.           lokális  változókba  helyezi,  majd  végiglépteti  a  soron.
  58.           Minden  lépésnél  a középsô sor középsô elemét vizsgálja meg
  59.           a  program,  hogy van-e benne zaj. Ehhez egy maszkot képez a
  60.           kilenc  elembôl:  minden  1-es  bitbôl három szomszédos 1-es
  61.           bitet  képez.  Majd  logikai  @KÉS@N  mûveletet végez a maszk és
  62.           az  eredeti (középsô) elem között, így ha a vizsgált elemben
  63.           van  zaj,  akkor  az  törlôdik.  Amikor  a  négyzetrács  egy
  64.           szélsô  elemét  kell  vizsgálni, akkor a nem létezô szomszéd
  65.           elemeket nullával helyettesíti a program."
  66.  
  67.           A  szerencse  kegyeltje, s így a hónap nyertese Tóth Zoltán;
  68.           a  CT  BBS-en  Maleskovits  Péter Pascal programja található
  69.           meg.
  70.  
  71.  
  72.                               @VNehéz szakaszok@N
  73.  
  74.           Kemény  diónak  bizonyult  júliusi rejtvényünk, melyet Varga
  75.           József   olvasónk   javasolt   kitûzésre,   s   amely  annak
  76.           eldöntését   kívánta   meg,   hogy   a   síkban   kezdô-  és
  77.           végpontjának  koordinátáival  megadott  @KN@N  darab  szakaszhoz
  78.           található-e  olyan  egyenes,  amely  minden szakaszon átmegy
  79.           (belsô   vagy  végponton).  Olvasóink  nem  hagytak  cserben
  80.           bennünket,  érkezett  három  megfejtés,  de sajnos egyik sem
  81.           hiba  nélküli, amire rovatunk több éves történetében még nem
  82.           volt   példa.   ùgy   tûnik,   megfejtôinknek  nem  sikerült
  83.           megtalálniuk   a  megfelelô  algoritmust,  mert  programjaik
  84.           viszonylag    egyszerû    tesztadatokon   véreztek   el.   A
  85.           szakaszokat  számnégyesekkel  jelölve,  a teszteredmények: a
  86.           (0,0,1,0),  (2,0,3,0),  (2,1,3,1)  szakaszokra  D.A. és P.A.
  87.           programja  igen,  T.L.  programja  nem  választ adott, míg a
  88.           (0,0,1,0),   (2,1,3,1),   (4,2,5,2)   szakaszokra   a  fenti
  89.           sorrendben  a  válaszok: igen, nem, nem; tehát egyik program
  90.           sem  kezelte  jól  ezen  --  és  más hasonló -- eseteket. (A
  91.           mellékelt    leírásokból   az   következtethetô   ki,   hogy
  92.           megfejtôink   gondosan  sokkal  több,  kimondottan  rafinált
  93.           elhelyezkedésû   szakaszon  próbálták  ki  programjaikat,  a
  94.           fentiekhez hasonló elemi esetek elkerülték figyelmüket.)
  95.  
  96.           A   látszólagos   sikertelenségen   felbuzdulva   az   elôre
  97.           menekülés    startégiáját   választjuk,   s   nehezítjük   a
  98.           feladatot.   (A  matematika  nem  egy  olyan  tételt  ismer,
  99.           amelyet  könnyebb  általánosítva,  ""nehezítve" bizonyítani,
  100.           mint eredeti formájában.)
  101.  
  102.           Végezetül   nehány   elegyes   megjegyzés,   halk   kérés  a
  103.           megoldásokkal  kapcsolatban.  A beküldött programok esetében
  104.           soha   nem   elégszünk  meg  a  listák  ""szárazon"  (értsd:
  105.           papíron)  történô  nézegetésével  (elegánsan:  elemzésével),
  106.           hanem  mindig  ki  is próbáljuk futás közben azokat. Viszont
  107.           gyakran  kapunk  több  oldalas  listákat,  papiron...  Éppen
  108.           ezért  okozott  nagy  örömet,  hogy  immár  BBS-en is kapunk
  109.           megoldásokat,    kérjük,   aki   teheti,   éljen   ezzel   a
  110.           lehetôséggel.    Sajnos,   néha   késünk   a   megfejtéseket
  111.           tartalmazó   lemezek   visszaküldésével,   de   azért   arra
  112.           buzdítanánk  olvasóinkat,  hogy ha nem BBS-en, akkor lemezen
  113.           küldjék   munkáikat.   Persze  örömmel  fogadjuk  a  papíron
  114.           küldött  listákat  is,  de  ha  lehetne, akkor jó minôségben
  115.           nyomtatva, hogy legyen némi esély a beszkennelésre...
  116.  
  117.           @KBánhegyesi Zoltán@N
  118.  
  119.  
  120.  
  121.                               @Vùj rejtvényünk@N
  122.  
  123.                               @VIsmét szakaszok@N
  124.  
  125.           Varga  József  feladatát  némileg  átalakítva újra kitûzzûk:
  126.           Adott    @KN@N    szakasz    a   síkban,   például   kezdô-   és
  127.           végpontjának   koordinátáival.   îrjunk   programot,   amely
  128.           választ  ad  arra  a kérdésre, hogy húzható-e olyan egyenes,
  129.           amely   minden  szakaszon  átmegy  (belsô  vagy  végponton).
  130.           Amennyiben   van  ilyen  egyenes,  legalább  egy  egyenletét
  131.           (pontjait, rajzát stb.) adja meg a program.
  132.  
  133.  
  134.           Beküldési határidô: 1994. novenber 25.